#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#include<iostream>
#define MAX_SIZE 500
#define TRUE 1
#define FALSE 0
using namespace std;
typedef int KeyType;
typedef int OtherType;

typedef struct{
    KeyType key;//定义一个key
    OtherType data;//定义data用来记录信息
}RecordType;//定义相应结构体
//下面是堆建立
typedef struct{
    RecordType r[MAX_SIZE+1];
    int length;
}SortType;


void  sift(RecordType  r[],  int k, int m);
void  crt_heap(RecordType r[], int length );
void  SelectionSort(RecordType  r[],int length);
void  Insertsort(SortType *H);
void  sift(RecordType  r[],  int k, int m);//筛选算法
void  QuickSort(SortType *H,int s,int t);
int   Division(RecordType a[],int l,int h);
int   Find(SortType *H,int key);

void  sift(RecordType  r[],  int k, int m)//筛选算法
{
    /*假设r[k..m]是以r[k]为根的完全二叉树，且分别以r[2k]和r[2k+1]为根的左、右子树为大根堆，调整r[k]，使整个序列r[k..m]满足堆的性质*/
    RecordType t;
    int i,j,x;
    bool finished;
    finished=FALSE;
    t=r[k];      //暂存根记录
    x=r[k].key;
    i=k;
    j=2*i;
    while(j<=m && !finished)
    {
        if(j<m && r[j].key <r[j+1].key )//若存在右子树,且右子树根的关键字大,则沿右分支筛选
            j=j+1;
        if(x>=r[j].key )
            finished=TRUE;        //筛选完毕
        else                        //继续筛选
        {   r[i]=r[j];
            i=j;
            j=2*i;
        }
    }
    r[i]=t;    //r[k]填入到当前位置
}

void   crt_heap(RecordType r[], int length )
/*对记录数组r建堆，length为数组的长度*/
{
    int n,i;
    n=length;
    for(i=n/2;i>=1;--i)//从第i个位置开始筛选建堆
        sift(r,i,n);
}

void  SelectionSort(RecordType  r[],int length)
//对r[1..n]进行堆排序，执行本算法后，r中记录按关键字由小到大有序排列 //
{
    crt_heap(r,length);
    RecordType t;
    int n,i;
    n=length;
    for(i=n;i>=2;--i)//将堆顶记录和堆中的最后一个记录互换
    {
        t=r[1];
        r[1]=r[i];
        r[i]=t;
        sift(r,1,i-1);  //使r[1..i-1]变成堆
    }
} // SelectionSort //

void Insertsort(SortType *H)//直接插入排序(/up)
{
    int i,j;
    RecordType temp;
    RecordType * t=H->r;//简化for循环中语言表达
    for(i=2;i<=H->length;++i)
    {
        temp=t[i];
        for(j=i-1;temp.key<t[j].key&&j>0;j--)
            //寻找插入位置（后->前）
            t[j+1]=t[j];
            if(j!=i-1)
                t[j+1]=temp;//
                }

}//insertsort

void QuickSort(SortType *H,int s,int t)
//递增顺序对H->r[s..t]进行快速排序
{
    int p;
    if(s<=t-1)//长度大于等于1
    {
        p=Division(H->r,s,t);//一次划分
        QuickSort(H,s,p-1);//对轴左边进行递归排序
        QuickSort(H,p+1,t);//对轴右边进行递归排序
    }
}//QuickSort
int Division(RecordType a[],int l,int h)
{
    int p;
    a[0]=a[l];
    p=a[l].key;
    while(l<h)
    {
        while(l<h&&a[h].key>=p)
            --h;//右->左查找
        a[l]=a[h];
        while(l<h&&a[l].key<=p)
            ++ l;//左->右查找
        a[h]=a[l];
    }
    a[l]=a[0];
    return l;//返回下标
}
int Find(SortType *H,int key)
{
    int l=1,h=H->length,mid;
    while(l<=h)
    {
        mid=(l+h)/2;//向下取整
        if(key==H->r[mid].key)
            return mid;//search the key word
        else if(key<H->r[mid].key)
            h=mid-1;//寻找left边
        else l=mid+1;//寻找right边
    }return 0;
}//find

int main()
{
    int i,j,k,a[MAX_SIZE],key,answer,runtime;
    long Start,Stop,Timespace[4];
    SortType *H=NULL;
    H=(SortType*)malloc(sizeof(SortType));
    srand(time(NULL));
    printf("The number before sort：\n");
    for(i=1;i<=MAX_SIZE;i++)//播种500个随机数据
    {
        H->r[i].key=rand()%1000;
        a[i]=H->r[i].key;//复制数据
        printf("%4d ",H->r[i].key);
        j = i%14;
        if(j == 0){
            printf("\n");
        }
    }
    H->length=MAX_SIZE;
    Start=clock();
    QuickSort(H,1,H->length);
    Stop=clock();
    Timespace[1]=Stop-Start;
    for(runtime=0;runtime<=999;runtime++)//进行选择排序时，进行1000次排序
    {
        for(i=1;i<MAX_SIZE;i++)
        {
            H->r[i].key=a[i];
        }
        Start=clock();
        QuickSort(H,1,H->length);
        Stop=clock();
        Timespace[1]=Timespace[1]+Stop-Start;//记下完成快速排序所用时间
    }
    printf("\n");
    printf("This is the number after sort:\n");
    for(i=1;i<=MAX_SIZE;i++)
    {
        printf("%4d ",H->r[i].key);
        j=i%14;
        if(j==0)
        {
            printf("\n");
        }
    }
    printf("\n");
    printf("********Design by 20154312*******\n");
    printf("********Average Time*******\n");
    printf("Use QuickSort at %d Project run %ldms\n",runtime,Timespace[1]);
    Timespace[2]=0;
   for(runtime=0;runtime<=999;runtime++)
   {
        for(i=1;i<MAX_SIZE;i++)
        {
            H->r[i].key=a[i];
        }
        Start=clock();
        SelectionSort(H->r,MAX_SIZE);
        Stop=clock();
        Timespace[2]=Timespace[2]+Stop-Start;
    }
    printf("Use SelectionSort at %d Project run %ldms\n",runtime,Timespace[2]);
    Timespace[3]=0;
    for(runtime=0;runtime<=999;runtime++)///进行直接插入排序时，进行1000次排序
    {
        for(i=1;i<MAX_SIZE;i++)
        {
            H->r[i].key=a[i];
        }
        Start=clock();
        Insertsort(H);
        Stop=clock();
        Timespace[3]=Timespace[3]+Stop-Start;
    }
    printf("Use InsertSort at %d Project run %ldms\n",runtime,Timespace[3]);
    printf("Keydown the number you want search\n");
    scanf("%d",&key);
    answer=Find(H,key);
    if(answer==0)
        printf("Sorry,nothing found\n");
    else
        printf("I found it!%d,it is the %d number\n",key,answer);
    printf("********Design by 20154312*******\n");
}